package com.dhx.algorithms.lru;

/**
 * @author dhx_
 * @className DoubleList
 * @date : 2023/02/17/ 19:28
 **/
public class DoubleList {
    /**
     * 头尾虚节点
     */
    private Node head, tail;

    /**
     * 链表元素数
     */
    private int size;

    public DoubleList() {
        // 初始化双向链表的数据
        head = new Node(0, 0);
        tail = new Node(0, 0);
        head.next = tail;
        tail.pre = head;
        size = 0;
    }

    /**
     * 在链表尾部添加节点 x，时间 O(1)
     * @param x 需要添加的node
     */
    public void addLast(Node  x) {
        x.pre = tail.pre;
        x.next = tail;
        tail.pre.next = x;
        tail.pre = x;
        size++;
    }

    /**
     * 删除链表中的 x 节点（x 一定存在） , 由于是双链表且给的是目标 Node 节点，时间 O(1)
     * @param x
     */
    public void remove(Node  x) {
        x.pre.next = x.next;
        x.next.pre = x.pre;
        size--;
    }

    /**
     * 删除链表中第一个节点，并返回该节点，时间 O(1)
     * @return
     */
    public Node removeFirst() {
        if (head.next == tail)
            return null;
        Node first = head.next;
        remove(first);
        return first;
    }

    /**
     * 返回链表长度，时间 O(1)
     * @return
     */
    public int size() { return size; }

}
